#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class treeColorGame {
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        chosen = x;
        dfs(root);
        int half = n / 2;
        // 对于选取的x计算其左右子树个数，将其与树总节点数/2做比较
        if (left > half || right > half || left + right < half)
            return true;
        else
            return false;
    }

    int dfs(TreeNode* root) {
        if (root == NULL)
            return 0;
        int leftCount = dfs(root->left);
        int rightCount = dfs(root->right);

        if (root->val == chosen) {
            left = leftCount;
            right = rightCount;
        }
        return leftCount + rightCount + 1;
    }
private:
    int left;
    int right;
    int chosen;
};


// 位运算记录伪回文序列
class palindromicPaths {
public:
    int pseudoPalindromicPaths(TreeNode* root) {
        count = 0;
        ans = 0;
        postOrder(root);
        return ans;
    }

    void postOrder(TreeNode* root) {
        if (root == nullptr)
            return;
        // 异或运算记录bit位对应数字出现次数奇（bit = 1）/偶（bit = 0）
        count ^= (1 << root->val);
        postOrder(root->left);
        postOrder(root->right);
        if (!root->left && !root->right) {
            if (count == 0 || (count & (count - 1)) == 0)
                // 如果全为偶或者只有一个奇数，则为回文串
                ans++;
        }
        // 当前root节点使用完毕，去掉其对count的影响
        count ^= (1 << root->val);
    }
private:
    int ans;
    int count;
};

// 分配硬币
/* 
 * 思路：肯定要从后往前遍历，也就是后序遍历，否则无法知道当前节点应该如何操作
 *      对于每一个节点，我留一个硬币，然后其余多出来/欠出来的硬币，把它交给自己的父节点/其余节点去处理
 *      对于每个多/欠的硬币，每个节点上都需要对左右子树节点的这些硬币进行处理，所以ans += 左子树移动次数 + 右子树移动次数
 */
class distribute {
public:
    int distributeCoins(TreeNode* root) {
        ans = 0;
        postOrder(root);
        return ans;
    }

    int postOrder(TreeNode* root) {
        if (root == nullptr)
            return 0;
        int leftMove = postOrder(root->left);
        int rightMove = postOrder(root->right);
        ans += abs(leftMove) + abs(rightMove);

        return root->val + leftMove + rightMove - 1;
    }
private:
    int ans;
};